package demo1;

public class MysingleList implements ILink{
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode head;
        public void create(){
            ListNode node1 = new ListNode(0);
            ListNode node2 = new ListNode(1);
            ListNode node3 = new ListNode(2);
            ListNode node4 = new ListNode(3);
            ListNode node5 = new ListNode(4);
            //做连接
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = node5;
            node5.next = null;//可以不加
            this.head = node1;
        }
        public void show(){
            ListNode node = this.head;
            while(node!=null){
                System.out.print(node.val+" ");
                node = node.next;
            }
            System.out.println();
        }
    public void show(ListNode newNode){
        ListNode node = newNode;
        while(node!=null){
            System.out.print(node.val+" ");
            node = node.next;
        }
        System.out.println();
    }

    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }

    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(head == null){
            head = node;
            return;
        }
        ListNode cur = head;
        while(cur.next != null){
            cur=cur.next;
        }
        cur.next = node;
    }

    @Override
    public void addIndex(int index, int data) {//任意位置前插入
        int len=size();
        if(index<0 || index>len){
            throw new IndexOutOfBoundsException();
        }
        if(index==0){
            addFirst(data);
        }
        if(index==len){
            addLast(data);
        }
        ListNode cur=searchIndex(index);
        if(cur==null){
            return;
        }
        ListNode node=new ListNode(data);
        node.next=cur.next;
        cur.next=node;
    }
    private ListNode searchIndex(int index){//寻找位置的前一个
            int len=size();
            if(index<0 || index>len){
                return null;
            }
            ListNode cur = head;
            int count=0;
            while(count!=index-1){
                cur=cur.next;
                count++;
            }
            return cur;
    }


    @Override
    public boolean contains(int key) {//查找关键字是否在链表中
            ListNode node = this.head;
            while(node!=null){
                if(node.val==key){
                    return true;
                }
                node = node.next;
            }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head==null){
            return;
        }
        if(head.val==key){
            head=head.next;
            return;
        }
        ListNode cur = head;
        while(cur.next!=null){
            if(cur.next.val==key){
                cur.next=cur.next.next;
                return;
            }
            cur=cur.next;
        }

    }

    @Override
    public void removeAllKey(int key) {//删除所有关键字
        if(head==null){
            return;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while(cur!=null){
            if(cur.val==key){
                prev.next=cur.next;
            }else{
                prev=prev.next;
            }
            cur=cur.next;
        }
        if(head.val==key){
            head=head.next;
        }
    }

    @Override
    public int size() {
        int count = 0;
        ListNode node = this.head;
        while(node!=null){
            count++;
            node = node.next;
        }
        return count;
    }

    @Override
    public void clear() {
        head=null;
    }


    public ListNode reverseList(ListNode head){//反转链表
            //方法一：递归
            if(head==null){
                return null;
            }
            if(head.next==null){
                return head;
            }
            ListNode newHead = reverseList(head.next);
            head.next.next = head;
            head.next=null;
            return newHead;
    }
    public ListNode reverseList1(ListNode head){//反转链表
            //方法二
        if(head==null){
            return null;
        }
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode temp=cur.next;
            cur.next=head;
            head=cur;
            cur=temp;
        }
        return head;

    }
    public ListNode reverseList2(ListNode head){
            //方法三
        if(head==null){
            return null;
        }
        ListNode cur=head;
        ListNode prev=null;
        while(cur!=null){
            ListNode temp=cur.next;
            cur.next=prev;
            prev=cur;
            cur=temp;
        }
        return prev;
    }

    public ListNode middleNode(){//链表中间数
            if(head==null){
                return null;
            }
            if(head.next==null){
                return head;
            }
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }
            return slow;
    }

    public int kthToLast(int k){//返回倒数第k个节点的值
            if(k<0||k>size()){
                return -1;
            }
            ListNode fast=head;
            ListNode slow=head;
            int count=0;
            while(count!=k-1){
                fast=fast.next;
                count++;
            }
            while(fast.next!=null){
                fast=fast.next;
                slow=slow.next;
            }
            return slow.val;
    }

    public ListNode partition(int x) {//小于x的数排左边，大于x的排右边
            ListNode newListNodeHead1=null;//链表1头
            ListNode newLIstNodeLast1=null;//链表1尾
            ListNode newListNodeHead2=null;//链表2头
            ListNode newLIstNodeLast2=null;//链表2尾
            ListNode cur=head;
            while(cur!=null){
                if(cur.val<x){
                    if(newListNodeHead1==null){
                        newListNodeHead1=newLIstNodeLast1=cur;
                    }else{
                        newLIstNodeLast1.next=cur;
                        newLIstNodeLast1=newLIstNodeLast1.next;
                    }
                }else{
                    if(newListNodeHead2==null){
                        newListNodeHead2=newLIstNodeLast2=cur;
                    }else{
                        newLIstNodeLast2.next=cur;
                        newLIstNodeLast2=newLIstNodeLast2.next;
                    }
                }
                cur=cur.next;
            }
            if(newListNodeHead1==null){
                return newListNodeHead2;
            }
            newLIstNodeLast1.next=newListNodeHead2;
            if(newListNodeHead2!=null){
                newLIstNodeLast2.next=null;
            }
            return newListNodeHead1;
    }
    public boolean Palindrome(){//判断链表是否为回文结构
            if(head==null){
                return false;
            }
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){//找中间节点
                fast=fast.next.next;
                slow=slow.next;
            }
            ListNode cur=slow;
            while(cur!=null){//反转链表
                ListNode curN=cur.next;
                cur.next=slow;
                slow=cur;
                cur=curN;
            }
            while(head!=slow){

                if(head.val!=slow.val){
                    return false;
                }
                if(head.next==slow){//这里可以不要，因为上面反转的时候是不是从next开始的
                    return true;
                }
                slow=slow.next;
                head=head.next;
            }
            return true;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB){//相交链表节点
            int lenA=0,lenB=0;
            ListNode pl=headA;
            ListNode ps=headB;
            while(pl!=null){
                lenA++;
                pl=pl.next;
            }
            pl=headA;
            while(ps!=null){
                lenB++;
                ps=ps.next;
            }
            ps=headB;
            int len=lenA-lenB;
            if(len<0){
                pl=headB;
                ps=headA;
                len=lenB-lenA;
            }
            while(len!=0){
                pl=pl.next;
                len--;
            }
            while(pl!=ps){
                pl=pl.next;
                ps=ps.next;
            }
            //还需考虑没有交点的情况
            if(pl==null){
                return null;
            }
            return pl;
    }
    public boolean hasClcy(){//判断一个链表是否为有环
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
                if(fast==slow){
                    return true;
                }
            }
            return false;
    }
    public int hasClcyNode(){//链表环的进入口节点
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }
        if(fast==null||fast.next==null){
            return -1;
        }
        fast=head;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast.val;
    }
    public void creatLoop(){
            ListNode cur=head;
            while(cur.next!=null){
                cur=cur.next;
            }
            cur.next=head.next;
    }
}
